#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
    }
    int rob1(vector<int>& nums, int left, int right)
    {
        if (left > right)
        {
            return 0;
        }
        vector<int> f(right - left + 1);
        vector<int> g(right - left + 1);
        f[0] = nums[left];
        for (int i = 1; i < right - left + 1; i++)
        {
            f[i] = nums[left + i] + g[i - 1];
            g[i] = max(g[i - 1], f[i - 1]);
            cout << f[i] << " " << g[i] << endl;

        }
        cout << f[right - left] << " " << g[right - left] << endl;
        return max(f[right - left], g[right - left]);
    }
};